/**
 * 累加数
 *
 *
 * 累加数 是一个字符串，组成它的数字可以形成累加序列。
 *
 * 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
 *
 * 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
 *
 * 说明：累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
 *
 * 输入："112358"
 * 输出：true
 * 解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
 *
 * 输入："199100199"
 * 输出：true
 * 解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
 */
public class Num306 {

    public static void main(String[] args) {
        System.out.println(isAdditiveNumber("1002003005008001300"));
    }

    public static boolean isAdditiveNumber(String num) {
        int firstLen = 1, secondLen = 1,thirdLen=1;
        if (num.length()<3 ) {
            return false;
        }
        //第一次计算随机性较大
        for (; firstLen + secondLen + thirdLen <= num.length(); firstLen++) {
            for (; true; secondLen++) {
                long firstNum = getNumber(num, 0, firstLen),
                        secondNum = getNumber(num, firstLen, secondLen),
                        thirdNum = firstNum + secondNum; //正确大小
                thirdLen = getLen(firstNum + secondNum);//正确长度
                if (firstLen + secondLen + thirdLen <= num.length()) {
                    if (thirdNum == getNumber(num, firstLen + secondLen, thirdLen)) {
                        if (isAccumulation(num, firstLen, secondLen, 0)) {
                            return true;
                        }
                    }
                } else {
                    break;
                }
            }
            if (secondLen == 1) {
                break;
            } else {
                secondLen = 1;
            }
        }
        return false;
    }

    //判断后续是否是累加数,baseLen为基础长度(已经判断完的长度)
    private static boolean isAccumulation(String num, int firstLen, int secondLen,int baseLen) {
        long firstNum = getNumber(num, baseLen, firstLen),
                secondNum = getNumber(num, baseLen + firstLen, secondLen);
        int thirdLen = getLen(firstNum + secondNum );
        long thirdNum = getNumber(num,baseLen+firstLen+secondLen,thirdLen);

        if (firstNum + secondNum == thirdNum) {
            if (firstLen > 1) {
                if (getNumber(num, baseLen, 1) == 0) {
                    return false;
                }
            }
            if (secondLen > 1) {
                if (getNumber(num, baseLen+firstLen, 1) == 0) {
                    return false;
                }
            }
            if (thirdLen > 1) {
                if (getNumber(num, baseLen+firstLen+secondLen, 1) == 0) {
                    return false;
                }
            }
            if (baseLen + firstLen + secondLen + thirdLen == num.length()) {
                return true;
            } else if (baseLen + firstLen + secondLen + thirdLen + thirdLen <= num.length()) {
                return isAccumulation(num, secondLen, thirdLen, baseLen + firstLen);
            }
        }
        return false;
    }

    //获取数字
    private static long getNumber(String num, int start, int len) {
        char[] charArray = num.toCharArray();
        long result=0;
        int j = 1;
        for (long i = 1; i <= Math.pow(10,len-1); i*=10,j++) {
            result += (charArray[start + (len - 1) - (j-1)]-'0') * i;
        }
        return result;
    }

    //获取长度
    private static int getLen(long num) {
        if (num == 0) {
            return 1;
        }
        int len = 0;
        for (; num > 0; num/=10,len++) { }
        return len;
    }
}
